#pragma once

#include <vector>
#include <map>
#include <functional>
#include <cassert>

/** A mapped priority queue, used for searching tags
 *  and LRU blocks.
 *  This optimization provides about 6 times speed up over
 *  naive implementation (linear search) when trying all
 *  possible combinations of (C, B, S, WP, V).
 */
template <typename K, typename D, typename DC = std::less<D>, typename KC = std::less<K> >
class pqueue
{
public:
  typedef std::pair<K, D>  pair_type;
  typedef K                key_type;
  typedef D                data_type;
  typedef std::vector<pair_type> heap_type;
public:
  DC dless_;
  KC kless_;
  std::map<K, int, KC> idxs_;
  std::vector<pair_type> heap_;

  void upHeap(int pos);
  void downHeap(int pos);
  void setPos(int pos, const pair_type& x) { assert(pos >= 0 && pos < size()); heap_[pos] = x; idxs_[x.first] = pos; }
  bool less(const pair_type& p1, const pair_type& p2) const { return dless_(p1.second, p2.second); }
public:
  pqueue(const DC& dless = DC(), const KC& kless = KC())
    : dless_(dless), kless_(kless), idxs_(kless_) { /*dless.print();*/ }

  /** min heap (LRU element) */
  const D& min() const { assert(size() > 0); return heap_[0].second; }
  const K& minKey() const { assert(size() > 0); return heap_[0].first; }
  /** check key existence */
  bool contains(const K& k) const { return idxs_.find(k) != idxs_.end(); }
  /** queue size */
  int size() const { return heap_.size(); }
  /** access data using key */
  const D& operator[](const K& k) const { assert(contains(k)); return heap_[idxs_.find(k)->second].second; }
  /** access all data in heap order */
  const std::vector<pair_type>& heap() const { return heap_; }

  /** push a key, data pair to the queue */
  pqueue& push(const K &k, const D &d);
  /** replace data corresponding to a key */
  pqueue& replace(const K &k, const D &d, bool check = true);
  /** remove key and the corresponding data from queue */
  pqueue& remove(const K &k);

  void print() const;
};

#include "pqueue_impl.h"
